package breakthrough.AlphaBetaPlayer;

import game.GameState;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

import breakthrough.BreakthroughMove;
import breakthrough.BreakthroughState;
import breakthrough.AlphaBetaPlayer.Evaluation.ScoredBreakthroughState;

public class AlphaBeta {
	private int maxDepth;
	private boolean stop;
	
	public AlphaBeta(int maxDepth) {
		this.maxDepth = maxDepth;
		this.stop = false;
	}
	
	/**
	 * Runs an alpha beta search with a depth limited of maxDepth
	 * 
	 * @param board The BreakthroughState to start the search
	 * @return A BreakthroughMove that is the best possible situation for the given search depth
	 */
	public BreakthroughMove alphaBeta(BreakthroughState board) {
		ScoredBreakthroughState temp;
		if (board.who == GameState.Who.HOME) { 
			temp = this.maxValue(board, 0, Double.NEGATIVE_INFINITY, Double.POSITIVE_INFINITY);
		} 
		else {
			temp = this.minValue(board, 0, Double.NEGATIVE_INFINITY, Double.POSITIVE_INFINITY);
		}

		return temp.getMove();
	}
	
	/**
	 * Runs the alpha beta search on a MAX child (from the user's perspective)
	 * 
	 * @param board The current state at this iteration of alpha beta
	 * @param depth The current depth of this node
	 * @param alpha The current value of alpha
	 * @param beta The current value of beta
	 * @return A ScoredBreakthroughState, which should have a move and its associated utility that is maximized
	 */
	private ScoredBreakthroughState maxValue(BreakthroughState board, int depth, double alpha, double beta) {		
		List<BreakthroughMove> moves = this.getSuccessors(board);
		if (depth >= this.maxDepth || moves.isEmpty() || this.isTerminal(board) || this.stop) {
			return new ScoredBreakthroughState(board);
		}
		
		ScoredBreakthroughState utility = new ScoredBreakthroughState(Double.NEGATIVE_INFINITY);
		
		for (BreakthroughMove successor : moves) {
			BreakthroughState boardClone = (BreakthroughState) board.clone();
			boardClone.makeMove(successor);
			
			ScoredBreakthroughState minVal = this.minValue(boardClone, depth + 1, alpha, beta);
			minVal.setMove(successor);
			
			if (minVal.getUtility() > utility.getUtility()) {
				utility = minVal;
			}
			
			if (utility.getUtility() >= beta) {
				return utility;
			}
			
			alpha = Math.max(alpha, utility.getUtility());
		}
		
		return utility;
	}
	
	/**
	 * Runs the alpha beta search on a MIN child (from the opponent's perspective)
	 * 
	 * @param board The current state at this iteration of alpha beta
	 * @param depth The current depth of this node
	 * @param alpha The current value of alpha
	 * @param beta The current value of beta
	 * @return A ScoredBreakthroughState, which should have a move and its associated utility that is minimized
	 */
	private ScoredBreakthroughState minValue(BreakthroughState board, int depth, double alpha, double beta) {
		List<BreakthroughMove> moves = this.getSuccessors(board);
		if (depth >= this.maxDepth || moves.isEmpty() || this.isTerminal(board) || this.stop) {
			return new ScoredBreakthroughState(board);
		}
		
		ScoredBreakthroughState utility = new ScoredBreakthroughState(Double.POSITIVE_INFINITY);
		
		for (BreakthroughMove successor : moves) {
			BreakthroughState boardClone = (BreakthroughState) board.clone();
			boardClone.makeMove(successor);
			
			ScoredBreakthroughState maxVal = this.maxValue(boardClone, depth + 1, alpha, beta);
			maxVal.setMove(successor);
			
			if (maxVal.getUtility() < utility.getUtility()) {
				utility = maxVal;
			}
			
			if (utility.getUtility() <= alpha) {
				return utility;
			}
			
			beta = Math.min(beta, utility.getUtility());
		}
		
		return utility;
	}
	
	private boolean isTerminal(BreakthroughState board) {
		for (int i = 0; i < BreakthroughState.N; i++) {
			if (board.board[0][i] == BreakthroughState.awaySym || board.board[BreakthroughState.N - 1][i] == BreakthroughState.homeSym) {
				return true;
			}
		}
		
		return false;
	}
	
	
	/**
	 * Retrieves a list of valid moves given the current state
	 * 
	 * @param board The current BreakthroughState to be evaluated
	 * @return A list of BreakthroughMoves that are valid
	 */
	private List<BreakthroughMove> getSuccessors(BreakthroughState board) {
		ArrayList<ScoredBreakthroughState> successorBoards = new ArrayList<ScoredBreakthroughState>();
		ArrayList<BreakthroughMove> list = new ArrayList<BreakthroughMove>();
		
		BreakthroughMove mv = new BreakthroughMove();
		int dir = board.who == GameState.Who.HOME ? +1 : -1;
		
		for (int r=0; r < BreakthroughState.N; r++) {
			for (int c=0; c < BreakthroughState.N; c++) {
				mv.startRow = r;
				mv.startCol = c;
				mv.endingRow = r+dir; mv.endingCol = c;
				
				if (board.moveOK(mv)) {
					successorBoards.add(getScoredSuccessor(board, mv));
				}
				mv.endingRow = r+dir; mv.endingCol = c+1;
				if (board.moveOK(mv)) {
					successorBoards.add(getScoredSuccessor(board, mv));
				}
				mv.endingRow = r+dir; mv.endingCol = c-1;
				if (board.moveOK(mv)) {
					successorBoards.add(getScoredSuccessor(board, mv));
				}
			}
		}
		
		Collections.sort(successorBoards);
		
		if (board.who == GameState.Who.HOME) {
			for(int i=0; i<successorBoards.size(); i++) {
				list.add(successorBoards.get(i).getMove());
			}
		}
		else {
			for(int i=successorBoards.size()-1; i>=0; i--) {
				list.add(successorBoards.get(i).getMove());
			}
		}
		
		
		return list;
	}
	
	public void setStop(boolean stop) {
		this.stop = stop;
	}
	
	private ScoredBreakthroughState getScoredSuccessor(BreakthroughState board, BreakthroughMove mv) {
		BreakthroughState successorBoard = (BreakthroughState) board.clone();
		BreakthroughMove moveClone = (BreakthroughMove) mv.clone();
		successorBoard.makeMove(moveClone);
		ScoredBreakthroughState scoredSuccessor = new ScoredBreakthroughState(successorBoard);
		scoredSuccessor.setMove(moveClone);
		return scoredSuccessor;
	}
}
